package ShellSort;


/*
*        希尔排序是插入排序的更高效版本
*        希尔排序的基本原理是：将整个待排序的记录序列进行分割，针对被分割的子序列进行直接插入排序
*                           当整个序列中的记录 “基本有序” 后，此时在针对全体记录进行依次的直接插入排序
*
*/

import java.lang.reflect.Array;
import java.util.Arrays;

public class Shell {

    // 这里将实现核心排序算法
    // 在这里，相较于 直接插入排序 需要多传入一个变量来针对数组进行分割
    public static void ShellSort(int arr[], int grp){
        // 这里的核心代码也就是针对 直接插入排序 的变形操作
        // 需要注意的是，这里的 i 不在是从 1 开始
        // 这里的 i 是从当前分组的位置进行的
        for(int i = grp; i < arr.length; i++) {
            // 同样的，定义一个变量记录当前 i 位置的元素
            int flag = arr[i];

            // 同样的定义一个变量用来记录 grp 之前一个位置的元素信息
            int j = i - grp;

            // 同样的将 j 位置的元素和 flag 记录的 i 位置的元素进行比较
            // 需要注意的是，这里 j 的递减是从 grp 被分割的位置开始的
            // 一定要注意的是这里的 j 是可以等于 0 的
            // 否则就会出现 数组元素少判断的情况！！！
            for(; j >= 0; j -= grp) {
                // 此时进行交换操作
                if(arr[j] > flag) {
                    // 此时就需要将 arr[j] 位置的值向后移动
                    arr[j + grp] = arr[j];
                }else {
                    // 当不满足条件时，此时直接跳出
                    break;
                }
            }
            // 此时将需要存放较小值的位置进行设置
            // 这里其实和 插入排序 有着异曲同工之处
            // 在 插入排序 中，这里是 arr[j + 1] = flag 这是因为在 for 循环中 最后的 -- 操作会让 j 的实际位置前移一位
            // 同样的 这里的 Shell 排序会在 for 循环结束后多减一次 grp
            // 所以代码如下：
            arr[j + grp] = flag;
        }
    }

    // 这里处理对于数组的分割操作
    public static int[] split (int arr[]) {
        int gap = arr.length;
        while(gap > 1) {
            // 每次进行分割后，都进行一次排序操作
            ShellSort(arr, gap);
            // 只要分组元素大于 1 就不断进行分组操作
            gap /= 2;
        }

        // 最后一次进行最终单个位置上的 希尔排序
        ShellSort(arr,1);
        return arr;
    }

    public static void main(String[] args) {
        int[] arr = {6,4,5,7,8,3,44,2,1};

        System.out.println(Arrays.toString(split(arr)));
    }

}
